/*
 * @lc app=leetcode.cn id=475 lang=typescript
 *
 * [475] 供暖器
 */

// @lc code=start
function findRadius(houses: number[], heaters: number[]): number {
  // 这里返回的结果在[0,heaters.length]区间
  const binarySearch = (heaters: number[], target: number): number => {
    let l = 0;
    let r = heaters.length - 1;
    let mid: number;
    while (l < r) {
      mid = (r + l) >> 1;
      if (heaters[mid] >= target) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };

  heaters.sort((a, b) => a - b);

  let ans = 0;
  for (const num of houses) {
    // 二分查找第一个大于等于当前房子值的供暖器的位置
    let index = binarySearch(heaters, num);
    // let a = Math.abs(heaters[index] - num);
    // let b = Math.abs(index ? heaters[index - 1] - num : a + 1);
    // ans = Math.max(ans, Math.min(a, b));
    if (index === 0) {
      // 获取供暖器和房子之间的距离
      ans = Math.max(ans, Math.abs(heaters[index] - num));
    } else if (index === heaters.length) {
      // 房子超出了最大供暖器的位置，所以只能取最后一个供暖器和当前房子计算距离
      ans = Math.max(ans, Math.abs(heaters[index - 1] - num));
    } else {
      // 房子和当前供暖器位置，房子和之前供暖器的位置取最小值，表示取2个供暖器的最小辐射范围
      ans = Math.max(
        ans,
        Math.min(Math.abs(heaters[index] - num), Math.abs(heaters[index - 1] - num))
      );
    }
  }

  return ans;
}
// @lc code=end
